package hot100;


/*
 * Author：江松
 * Date：2023/4/15 10:27
 *
 *
 无重复字符的最长子串:
 1,动态规划：
 f(i)表示以第i个字符结尾的最长无重复子串大小,
 那么如果i-1-f(i-1)到i-1没有与i相同字符，可以转移fi=f(i-1)+1
 否则不能转移fi=i-j

2，滑动窗口（题解）：
模拟这种情况，可以看出是一个滑动窗口的模型
如果set没有重复，不断右移，如果有重复，就不断删除前面的直到不重复

 */

import java.util.HashSet;

public class Main3 {


    public int lengthOfLongestSubstring(String s) {
        int n=s.length();
        if(n==0)return 0;
        HashSet<Character>set=new HashSet<>();
        int l=0,r=0;
        int res=-1;
        while(l<=r&&r<n){
            if(!set.contains(s.charAt(r))){
                set.add(s.charAt(r));
                r++;
            }else {
                while(set.contains(s.charAt(r))){
                    set.remove(s.charAt(l));
                    l++;
                }
            }
            res=Math.max(res,r-l+1);
        }
        return res;
    }

    /*
    //动态规划
    public int lengthOfLongestSubstring(String s) {
        int n=s.length();
        if(n==0)return 0;
        int res=1;
        int f[]=new int[n];
        f[0]=1;
        for(int i=1;i<n;++i){
            char ch=s.charAt(i);
            int j;
            for(j=i-f[i-1];j<i;++j){
                if(s.charAt(j)==ch)break;
            }
            if(j!=i)f[i]=i-j;
            else f[i]=f[i-1]+1;

            res=Math.max(res,f[i]);
        }
        return res;
    }
    */
}
